import java.util.ArrayList;

public class UnionFind {
	private ArrayList<ArrayList<StarComponent>> id;
	
	public UnionFind(){
		
	}
	/**
	 * Create an empty union find data structure with N isolated sets.
	 * @throws java.lang.IllegalArgumentException if N < 0
	 */
	public UnionFind(ArrayList<StarComponent> starComponents) {
		id = new ArrayList<ArrayList<StarComponent>>();
		for (int i = 0; i < starComponents.size(); i++) {
			ArrayList<StarComponent> setOfStarComponents = new ArrayList<StarComponent>();
			setOfStarComponents.add(starComponents.get(i));
			id.add(setOfStarComponents);
		}
	}

	/**
	 * Return the id of component corresponding to object p.
	 * @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N
	 */
	public ArrayList<StarComponent> find(StarComponent p) {
		for (int i = 0; i < id.size(); i++) {
			if (id.get(i).contains(p)) {
				return id.get(i);
			}
		}
		return null;
	}

	/**
	 * Return the number of disjoint sets.
	 */
	public int count() {
		return id.size();
	}


	/**
	 * Are objects p and q in the same array list (set)?
	 */
	public boolean connected(StarComponent p, StarComponent q) {
		return find(p).equals(find(q));
	}

	public StarComponent getStarComponent(int index) {
		return id.get(index).get(0);
	}

	/**
	 * Replace sets containing p and q with their union.
	 * @throws java.lang.IndexOutOfBoundsException unless both 0 <= p < N and 0 <= q < N
	 */
	public void union(StarComponent p, StarComponent q) {
		ArrayList<StarComponent> i = find(p);
		ArrayList<StarComponent> j = find(q);
		if (i.equals(j)) return;

		if (i.size() < j.size()) {
			i.addAll(j);
			id.remove(j);
		}
		else {
			j.addAll(i);
			id.remove(i);
		}
	}
}